package String;

import java.util.Scanner;

/**
 * 经典KMP算法，核心分为两部分，一是next数组的求取，二是匹配过程中，j指针的回退。
 * 为什么比暴力解法快？因为i指针是不回退的，暴力求解时，i指针会随着不匹配时一直回退，造成效率低下
 */
public class StrStrImpl {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String ss = scan.next();
        String pp = scan.next();
        //String ss = "ABABDABACDABABCABD";
        //String pp = "ABABCABD";
        StrStrImpl solution = new StrStrImpl();
        System.out.println(solution.strStr(ss, pp));
    }
    public int strStr(String ss, String pp){
        if(pp.length()==0) return 0;
        int n = ss.length();
        int m = pp.length();

        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        //构建next数组,长度只跟子串有关
        int[] next = new int[m];
        //构造过程 i = 1，j = 0 开始，i 小于等于匹配串长度 -> 构造 i 从 1 开始
        for(int i = 1, j = 0; i < m; i++){
            //匹配不成功的则 j=next[j]
            while (j > 0 && p[i] != p[j]){
                j = next[j - 1];
            }
            //匹配成功先让j++
            if(p[i] == p[j]) j++;
            //更新next[i]并结束循环
            next[i] = j;
        }
        for(int i = 0, j = 0; i < n; i++){
            while(j > 0 && s[i] != p[j]){
                j = next[j - 1];
            }
            if(s[i] == p[j]){
                j++;
            }
            if(j == m){
                return i - m + 1;
            }
        }
        return -1;
    }
}
